class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 1;
        int right = nums.size()-1;
        int res = -1;
        while(left <= right)
        {
            int mid = (left+right) / 2;
            int cnt = 0;
            for(int i = 0; i < nums.size(); i++)
            {
                if(nums[i] <= mid)
                    cnt += 1;
            }
            if(cnt > mid)
            {
                right = mid-1;
                res = mid;
            }
            else
            {
                left = mid+1;
            }
        }

        return res;
    }
};

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int bitw = 31;
        int res = 0;
        while(!(nums.size()-1)<<bitw)
            bitw -= 1;
        for(int i = 0; i <= bitw; i++)
        {
            int x = 0;
            int y = 0;
            for(int j = 0; j < nums.size(); j++)
            {
                if(nums[j] & (1<<i))
                    x+=1;
                if(j>0 && (j&(1<<i)))
                    y+=1;
            }
            if(x>y)
                res |= (1<<i);
        }

        return res;
    }
};